/*
 * @lc app=leetcode.cn id=15 lang=cpp
 *
 * [15] 三数之和
 */

// @lc code=start
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>

using namespace std;
class Solution {
public:
//排序+双指针
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        int size = nums.size();
        if (size < 3)   
            return {};        
        vector<vector<int> >res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < size; i++){
            if (nums[i] > 0)    
                return res; // 第一个数大于 0，后面都是递增正数，不可能相加为零了
            // 去重：如果此数已经选取过，跳过
            if (i > 0 && nums[i] == nums[i-1])  
                continue;
            // 双指针在nums[i]后面的区间中寻找和为0-nums[i]的另外两个数
            int left = i + 1;
            int right = size - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > -nums[i])
                    right--;    // 两数之和太大，右指针左移
                else if (nums[left] + nums[right] < -nums[i])
                    left++;     // 两数之和太小，左指针右移
                else
                {
                    // 找到一个和为零的三元组，添加到结果中，左右指针内缩，继续寻找
                    res.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    // 去重：第二个数和第三个数也不重复选取
                    // 例如：[-4,1,1,1,2,3,3,3], i=0, left=1, right=5
                    while (left < right && nums[left] == nums[left-1])  left++;
                    while (left < right && nums[right] == nums[right+1])    right--;
                }
            }
        }
        return res;
    }
};
// @lc code=end

/**
 * @brief 暴力法超时
 * 
 * int judge(vector<int>& nums,int i,int j,int k) {
        return nums[i] + nums[j] + nums[k];
    }
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> temp;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        for(int i = 0;i < n-2;i++) {
            for(int j = i + 1;j < n-1;j++) {
                for(int k = j + 1;k < n;k++) {
                    if(judge(nums,i,j,k) > 0) {
                        break;
                    }
                    if(judge(nums,i,j,k) == 0) {
                        temp.push_back(nums[i]);
                        temp.push_back(nums[j]);
                        temp.push_back(nums[k]);
                        sort(temp.begin(),temp.end());
                        res.push_back(temp);
                        temp.clear();
                    }
                }
            }
        }
        //去重
        set<vector<int>> s(res.begin(), res.end());
        res.assign(s.begin(), s.end());
        //去重方法2
        //unique会把容器中连续相同的数放到后面并返回前面不重复数组的长度
        //sort(res.begin(),res.end());
        //res.erase(res.unique(res,begin(),res.end(),res.end());
        return res;
    }
 * 
 */

